#include "parse.h"
#include "compute.h"
#include "globals.h"
#include "check.h"

SYMBOLS LeftRecurSyms(TSymbol* Root, SYMBOLS Stack, SYMBOLS Checked);


/* MarkLeftRecursive() - identify left-recursive nonterminals
 *
 * NB: we are only marking nonterminals with simple/direct
 * left recursion that we expect to later get rewritten. Other
 * code will identify any more general left-recursive constructs
 * that the user must rewrite.
 */
void    MarkLeftRecursive(void)
    {
    SymIt   NonTerm = SymItNew(Globals.NonTerms);
    SYMBOLS List    = SymbolListCreate();

    Dump("MarkLeftRecursive()\n");
    while(SymbolIterate(&NonTerm))
        if(!SymbolIsEmpty(NonTerm.Symbol))
            {
            SYMBOLS Path = LeftRecurSyms(NonTerm.Symbol, NULL, NULL);

            if(SymbolListCount(Path) > 0)
                {
                if(Globals.Dump && Globals.Verbose)
                    {
                    DumpVerbose("Left recursion path: ");
                    SymbolListDump(stdout, Path, " ");
                    DumpVerbose("\n");
                    }
                NonTerm.Symbol->LeftRecursive   = TRUE;
                List    = SymbolListAdd(List, NonTerm.Symbol);
                }
            SymbolListDestroy(Path);
            }

    if(SymbolListCount(List) > 0)
        {
        Dump("MarkLeftRecursive() found %d left-recursive non-terminals: ", SymbolListCount(List));
        SymbolListDump(stdout, List, ", ");
        Dump("\n");
        }
    else
        Dump("MarkLeftRecursive() found no left-recursive non-terminals\n");
    SymbolListDestroy(List);
    }


/* MarkNullable() - flag all non-terminals that are nullable.
 *
 * For various operations, we will want to know which non-terminals
 * can derive the empty string, either directly or indirectly.
 * The flag TSymbol->Nullable keeps track of this, and that flag is
 * set in these routines. Note that no attempt at efficiency is made.
 *
 * Note that the Nullable flag was set (off) for terminals when they were
 * created.
 *
 */
static
int    IsNullable(SYMBOLS Visited, TSymbol* Symbol)
    {
    int         Result      = FALSE;    /* assume not known to be nullable */
    int         iSymbol;
    TRule**     Rover;

    if(SymbolGetBit(Symbol, SYM_TERMINAL) == FALSE && !SymbolListContains(Visited, Symbol))
        {
        SymbolListAdd(Visited, Symbol);     /* add to list to avoid cycles */
        Rover   = Symbol->Rules;
        if(Rover) for(; *Rover; ++Rover)
            {
            int         NSymbols;
            TRule*      Rule    = *Rover;

            NSymbols    = SymbolListCount(Rule->Symbols);
            for(iSymbol = 0; iSymbol < NSymbols; ++iSymbol)
                {
                TSymbol*    RhsSymbol = SymbolListGet(Rule->Symbols, iSymbol);

                if(!IsNullable(Visited, RhsSymbol))
                    break;
                }
            if(iSymbol >= NSymbols || NSymbols == 0)
                {
                Result = TRUE;
                break;
                }
            }
        }
    else if(SymbolGetBit(Symbol, SYM_TERMINAL))
        Result  = FALSE;

    return Result;
    }

void    MarkNullable(void)
    {
    SYMBOLS     Visited, Marked;
    TSymbol*    NonTerm;
    int         MoreFound, iNonTerm, NNonTerms;
    TRule*      Rule;
    TRule**     Rover;

    Dump("MarkNullable() starts\n");

    Marked          = SymbolListCreate();
    NNonTerms       = SymbolListCount(Globals.NonTerms);

    /* first, mark the directly nullable non-terminals */
    for(iNonTerm=0; iNonTerm < NNonTerms; ++iNonTerm)
        {
        NonTerm = SymbolListGet(Globals.NonTerms, iNonTerm);

        Rover = NonTerm->Rules;
        if(Rover) for(; (Rule=*Rover) != NULL; ++Rover)
            if(SymbolListCount(Rule->Symbols) <= 0)
                {
                NonTerm->Nullable    = TRUE;
                SymbolListAdd(Marked, NonTerm);
                break;
                }
        }
//printf("%d directly nullable\n", SymbolListCount(Marked));
//SymbolListDump(stdout, Marked, " ");

    /* second, for each non-terminal, attempt to mark it nullable.
     * repeat until no new non-terminals have been marked nullable
     */
    do  {
        SymIt   NonTerm     = SymItNew(Globals.NonTerms);

        MoreFound   = FALSE;
        while(SymbolIterate(&NonTerm))
            if(!NonTerm.Symbol->Nullable)
                {
                Visited     = SymbolListCreate();
                if(IsNullable(Visited, NonTerm.Symbol))
                    {
                    MoreFound           = TRUE;
                    NonTerm.Symbol->Nullable    = TRUE;
                    }
                SymbolListDestroy(Visited);
                }
        } while(MoreFound);
    SymbolListDestroy(Marked);
    if(Globals.Dump && Globals.Verbose)
        {
        int First = TRUE;

        Dump("Nullable non-terminals:");
        for(iNonTerm=0; iNonTerm < NNonTerms; ++iNonTerm)
            {
            NonTerm = SymbolListGet(Globals.NonTerms, iNonTerm);
            if(NonTerm->Nullable && !SymbolIsAction(NonTerm))
                {
                Dump("%s%s", First? " " : ", ", SymbolStr(NonTerm));
                First   = FALSE;
                }
            }
        fprintf(stdout, "\n");
        }
    Dump("MarkNullable() ends\n");
    }

/* MarkEmpty() - mark which non-terminals are empty (produce no symbols).
 *
 */
void    MarkEmpty(void)
    {
    SymIt   NonTerm = SymItNew(Globals.NonTerms);

    Dump("MarkEmpty starts\n");
    DumpVerbose("Empty symbols: ");
    while(SymbolIterate(&NonTerm))
        {
        RuleIt  Rules = RuleItNew(NonTerm.Symbol);
        while(RuleIterate(&Rules))
            if(!SymbolIsAction(Rules.ProdItem))
                break;
        if(Rules.Finished)
            {
            DumpVerbose("%s ", SymbolStr(NonTerm.Symbol));
            SymbolSetBit(NonTerm.Symbol, SYM_EMPTY);
            }
        }
    DumpVerbose("\n");
    Dump("MarkEmpty() ends\n");
    }

/*  AddFirst() - add FIRST(X) to existing FIRST set
 *
 */
int     AddFirst(SYMBOLS* ListPtr, TSymbol* ProdItem)
    {
    int     Result  = FALSE;

    /* FIRST(X) is just X, if X is a terminal */
    if(SymbolGetBit(ProdItem, SYM_TERMINAL))
        {
        if(!SymbolListContains(*ListPtr, ProdItem))
            {
            *ListPtr    = SymbolListAdd(*ListPtr, ProdItem);
            Result      = TRUE;
            }
        }
    /* otherwise, we have to add one set of symbols to another */
    else if(ProdItem->First)
        Result = SymbolListAddList(ListPtr, ProdItem->First);

    return Result;
    }

/* ClearFirstFollow() - clear the FIRST/FOLLOW sets.
 *
 *
 */
void    ClearFirstFollow(void)
    {
    TRule*  Rule;
    TRule** Rover;
    SymIt   NonTerm = SymItNew(Globals.NonTerms);

    while(SymbolIterate(&NonTerm))
        {
        SymbolListDestroy(NonTerm.Symbol->First);
        SymbolListDestroy(NonTerm.Symbol->Follow);
        NonTerm.Symbol->First               = NULL;
        NonTerm.Symbol->Follow              = NULL;
        NonTerm.Symbol->FirstFollowClash    = FALSE;

        Rover = NonTerm.Symbol->Rules;
        if(Rover) for(; (Rule=*Rover) != NULL; ++Rover)
            {
            SymbolListDestroy(Rule->First);
            Rule->First = NULL;
            }
        }
    }

/* ComputeFirst() - compute first sets.
 *
 * FIRST(X) is the set of terminals that begin the strings
 * you can derive from X.
 *
 * Note that we have to watch out for direct left recursion carefully.
 * When X -> X alpha, that rule does not contribute anything to FIRST(X),
 * UNLESS, X is nullable. In that case, FIRST(alpha) must be added
 * to FIRST(X).
 */
void    ComputeFirst(void)
    {
    TSymbol*    NonTerm;
    TSymbol*    ProdItem;
    TRule*      Rule;
    TRule**     Rover;
    int         MoreFound, iNonTerm, NNonTerms, iProdItem, NProdItems;

    NNonTerms   = SymbolListCount(Globals.NonTerms);
    /* do until nothing else can be added to any FIRST set */
    do  {
        MoreFound   = FALSE;
        /* for each non-terminal */
        for(iNonTerm = 0; iNonTerm < NNonTerms; ++iNonTerm)
            {
            NonTerm  = SymbolListGet(Globals.NonTerms, iNonTerm);

            Rover   = NonTerm->Rules;
            if(Rover) for(; (Rule=*Rover) != NULL; ++Rover)
                {
                NProdItems  = SymbolListCount(Rule->Symbols);
                for(iProdItem = 0; iProdItem < NProdItems; ++iProdItem)
                    {
                    ProdItem    = SymbolListGet(Rule->Symbols, iProdItem);
                    /* if it's a direct left recursive rule */
                    if(iProdItem == 0 && ProdItem == NonTerm)
                        if(NonTerm->Nullable)
                            continue;       /* add FIRST() of rest of rule */
                        else
                            break;
                    if(AddFirst(&Rule->First, ProdItem))
                        MoreFound   = TRUE;
                    if(AddFirst(&NonTerm->First, ProdItem))
                        MoreFound   = TRUE;
                    if(ProdItem->Nullable == FALSE)
                        break;
                    }
                /* if all items nullable or rule has no items */
                if(iProdItem >= NProdItems || NProdItems == 0)
                    Rule->Nullable  = TRUE;
                }
            }
        } while(MoreFound);
    }

/* AddToFollow() - add 'Follow' to FOLLOW set of 'This'.
 */
static
int     AddToFollow(TSymbol* This, TSymbol* Follow, int NoClash)
    {
    int     Result = FALSE;

    if(SymbolListContains(This->First, Follow))
        if(!NoClash)
            {
//            DumpVerbose("FIRST/FOLLOW clash for '%s' on '%s'\n", SymbolStr(This), SymbolStr(Follow));
            This->FirstFollowClash  = TRUE;
            }
    if(!SymbolListContains(This->Follow, Follow))
        {
        This->Follow = SymbolListAdd(This->Follow, Follow);
        Result  = TRUE;
        }
    return Result;
    }

/* AddFirsts() - add FIRST(X) to FOLLOW() set, where X is a sequence of production items
 */
static
int     AddFirsts(TSymbol* This, SYMBOLS Items, int iProdItem, int NoClash)
    {
    int     Result      = FALSE;
    int     NProdItems  = SymbolListCount(Items);

    /* for each item (symbol) in this production */
    for(; iProdItem < NProdItems; ++iProdItem)
        {
        TSymbol*    Item        = SymbolListGet(Items, iProdItem);
        SymIt       First       = SymItNew(Item->First);
        
        while(SymbolIterate(&First))
            if(AddToFollow(This, First.Symbol, NoClash))
                Result  = TRUE;

        /* only proceed to next item if this one derives epsilon */
        if(Item->Nullable == FALSE)
            break;
        }

    return Result;
    }
/* StrIsNullable() - is a string (list) of symbols nullable?
 */
static
int     StrIsNullable(SYMBOLS List, int iSymbol)
    {
    int     Result      = TRUE;
    int     NSymbols    = SymbolListCount(List);

    for(; iSymbol < NSymbols; ++iSymbol)
        {
        TSymbol*    Symbol = SymbolListGet(List, iSymbol);

        if(!Symbol->Nullable)
            {
            Result  = FALSE;
            break;
            }
        }

    return Result;
    }

/* ComputeFollow() - compute the FOLLOW() set of all non-terminals.
 *
 * This is standard LL(1) algorithm stuff, except for the complication
 * of our inclusion of operator precedence functionality. If a non-terminal
 * A is an "operator trigger", then we ignore the productions of A when
 * computing FOLLOW(A).
 */
void    ComputeFollow(void)
    {
    TSymbol*    NonTerm;
    TSymbol*    ProdItem;
    TSymbol*    Start;
    TRule*      Rule;
    TRule**     Rover;
    int         MoreFound, iNonTerm, NNonTerms, iProdItem, NProdItems;
    int         iLoop, MaxLoop;

    Start   = SymbolStart();
    assert(Start != NULL);
    
    /* put '$' in FOLLOW() set of start symbol */
    Start->Follow = SymbolListAdd(Start->Follow, EndSymbol);

    NNonTerms   = SymbolListCount(Globals.NonTerms);
    iLoop       = 0;
    MaxLoop     = NNonTerms * NNonTerms;
    /* do until nothing can be added to any FOLLOW set */
    do  {
        MoreFound   = FALSE;
        ++iLoop;
        assert(iLoop <= MaxLoop);   /* defense against infinite loop */
        /* for each nonterminal */
        for(iNonTerm = 0; iNonTerm < NNonTerms; ++iNonTerm)
            {
            NonTerm  = SymbolListGet(Globals.NonTerms, iNonTerm);
            if(NonTerm->OperatorTrigger)
                continue;

            /* for each rule in this nonterminal */
            Rover   = NonTerm->Rules;
            if(Rover) for(; (Rule = *Rover) != NULL; ++Rover)
                {
                int         DLR     = FALSE;

                NProdItems  = SymbolListCount(Rule->Symbols);

                /* if nonterm is nullable and rule is Direct Left Recursion */
//                if(NonTerm->Nullable && NProdItems > 1 && SymbolListGet(Rule->Symbols, 0) == NonTerm)
                if(NonTerm->Nullable && NProdItems > 1 && SymbolListGet(Rule->Symbols, 0) == NonTerm)
                    DLR     = TRUE;
                /* for each item in this rule */
                for(iProdItem = 0; iProdItem < NProdItems; ++iProdItem)
                    {
                    ProdItem    = SymbolListGet(Rule->Symbols, iProdItem);

                    if(SymbolGetBit(ProdItem, SYM_TERMINAL) == FALSE)
                        {
                        /* if it's not the last item in the rule */
                        if(iProdItem < (NProdItems-1))
                            /* if X is the list of symbols to right, add FIRST(X) to FOLLOW(this) */
                            if(AddFirsts(ProdItem, Rule->Symbols, iProdItem+1, (iProdItem==0) && DLR))
                                MoreFound   = TRUE;
                        /* if it is the last item, or items to right are nullable */
                        if(iProdItem == (NProdItems-1) || StrIsNullable(Rule->Symbols, iProdItem+1))
                            {
                            SymIt       Follow  = SymItNew(NonTerm->Follow);

                            while(SymbolIterate(&Follow))
                                if(AddToFollow(ProdItem, Follow.Symbol, FALSE))
                                    MoreFound   = TRUE;
                            }
//                            if(SymbolListAddList(&ProdItem->Follow, NonTerm->Follow))
//                                MoreFound   = TRUE;
                        }
                    }
                }
            }
        } while(MoreFound);
    }

/* ComputeEndsWith() - compute ends-with relation for all nonterminals
 *
 * ENDSWITH(X) is the set of all nonterminals that can appear at the
 * end of a string derived from X.
 *
 * Note that we do not automatically include X in ENDSWITH(X). If
 * X appears in ENDSWITH(X), that means X is right-recursive.
 */
void    ComputeEndsWith()
    {
    int         iQueue, iProdItem;
    TRule*      Rule;
    TRule**     Rover;
    SYMBOLS     Queue;
    TSymbol*    Trailing;
    TSymbol*    This;
    SymIt       NonTerm = SymItNew(Globals.NonTerms);

    if(Globals.Dump) printf("ComputeEndsWith()\n");
    while(SymbolIterate(&NonTerm))
        {
        This    = NonTerm.Symbol;
        iQueue  = -1;
        Queue   = NULL;
        do  {
            Rover   = This->Rules;
            if(Rover) for(; (Rule=*Rover) != NULL; ++Rover)
                {
                /* scan symbols in this production, backward from the right */
                iProdItem   = SymbolListCount(Rule->Symbols);
                while(--iProdItem >= 0)
                    {
                    assert(Rule->Symbols != NULL);
                    Trailing    = SymbolListGet(Rule->Symbols, iProdItem);
                    assert(Trailing != NULL);

                    if(SymbolGetBit(Trailing, SYM_TERMINAL) == FALSE)
                        Queue   = SymbolListAddUnique(Queue, Trailing);
                    if(!Trailing->Nullable)
                        break;
                    }
                }
            } while((This=SymbolListGet(Queue, ++iQueue)) != NULL);
#if 0
        printf("ENDSWITH(%s) = ", SymbolStr(NonTerm.Symbol));
        SymbolListDump(stdout, Queue, ", ");
        printf("\n");
#endif
        NonTerm.Symbol->EndsWith    = Queue;
        }
    }

/* ??? need detailed design of how conflicts are resolved.
 * ??? need ability to show detailed list of conflicts when dumping LL table.
 */
static
int   LLConflict(TSymbol* NonTerm, TSymbol* Terminal, int Existing, int New)
    {
    int     RuleToStore = New;
    TRule*  OldRule;
    TRule*  NewRule;
    TRule*  Stored      = NULL;

    OldRule     = NonTerm->Rules[Existing];
    NewRule     = NonTerm->Rules[New];

    if(NonTerm->Name.Text[0] == '`')    /* if this is a left-recursive rewrite symbol */
        {
        if(OldRule->Nullable && !NewRule->Nullable)
            {
            RuleToStore = New;
            Stored      = NewRule;
            }
        else if(NewRule->Nullable && !OldRule->Nullable)
            {
            RuleToStore = Existing;
            Stored      = OldRule;
            }
        }
    else
        {
        fprintf(stderr, "Nonterminal '%s': conflict on token %s\n",
                SymbolStr(NonTerm), SymbolStr(Terminal));
        fprintf(stderr, "Can't choose between the following two productions:\n");
        fprintf(stderr, " (rule %d)-> ", Existing);
        SymbolListDump(stderr, NonTerm->Rules[Existing]->Symbols, " ");
        fprintf(stderr, "\n");
        fprintf(stderr, " (rule %d)-> ", New);
        SymbolListDump(stderr, NonTerm->Rules[New]->Symbols, " ");
        fprintf(stderr, "\n");
//???        return 1;
        }
#if 0
    printf("%.*s(%.*s) reject epsilon for: ",
           NonTerm->Name.TextLen, NonTerm->Name.Text,
           Terminal->Name.TextLen, Terminal->Name.Text);
    assert(Stored != NULL);
    SymbolListDump(stdout, Stored->Symbols, " ");
    printf("\n");
#endif
    /* if we're going to clobber an existing rule */
    if(RuleToStore != Existing)
        {
        int     iRule;

        for(iRule = 0; iRule < SymbolListCount(NonTerm->InputTokens); ++iRule)
            {
            if(NonTerm->LLTable[iRule] == Existing)
                {
                NonTerm->LLTable[iRule]     = RuleToStore;
                break;
                }
            }
        assert(iRule < SymbolListCount(NonTerm->InputTokens));
        }
    return 0;
    }

/* AddLLTableRule() - Define rule to expand when non-terminal encounters given token.
 */
static
int    AddLLTableRule(TSymbol* NonTerm, TSymbol* InputToken, int iRule)
    {
    int     NTokens;
    int     ExistingRule;
    int     Conflict    = 0;
    int     OkToAddRule = FALSE;
    
    ExistingRule  = SymbolListContains(NonTerm->InputTokens, InputToken)-1;
    /* if we got a problem because grammar ain't LL(1) */
    if(ExistingRule >= 0)
        {
        ExistingRule    = NonTerm->LLTable[ExistingRule];
        LLConflict(NonTerm, InputToken, ExistingRule, iRule);
//        OkToAddRule = TRUE;
//        ++Conflict;
        }
    else
        OkToAddRule = TRUE;

    if(OkToAddRule)
        {
        NonTerm->InputTokens    = SymbolListAdd(NonTerm->InputTokens, InputToken);
        NTokens                 = SymbolListCount(NonTerm->InputTokens);
        NonTerm->LLTable        = (int*)realloc(NonTerm->LLTable, NTokens*sizeof(int));
        assert(NonTerm->LLTable != NULL);
        NonTerm->LLTable[NTokens-1] = iRule;
        }
    return Conflict;
    }

/* ComputeLLTable() - try to construct an LL parsing table.
 *
 * The "table" is actually distributed across the non-terminals in the
 * symbol table. Each non-terminal contains two parallel arrays. InputTokens
 * is an array of the input tokens that are legal when that non-terminal is
 * on top of the parsing stack. LLTable is a parallel array of integers, where
 * each integer identifies the rule of that non-terminal associated with
 * the corresponding input token.
 */
void    ComputeLLTable(void)
    {
    int         NNonTerms, iTerm, iRule;
    TSymbol*    NonTerm;
    TSymbol*    InputToken;
    TSymbol*    Start;
    int         ErrorCount = 0;

    Start   = SymbolStart();
    
    /* for each non-terminal */
    NNonTerms      = SymbolListCount(Globals.NonTerms);
    for(iTerm = 0; iTerm < NNonTerms; ++iTerm)
        {
        NonTerm     = SymbolListGet(Globals.NonTerms, iTerm);

        assert(RuleCount(NonTerm) > 0);    /* sanity check */

        /* if it belongs to operator precedence grammar or is implicit start symbol */
        if(NonTerm->OperatorTrigger || NonTerm == Start)
            continue;   /* then skip it */
        
        /* for each rule (aka production) of this non-terminal */
        for(iRule = 0; iRule < RuleCount(NonTerm); ++iRule)
            {
            int         NFirst, iFirst;
            TRule*      Rule = NonTerm->Rules[iRule];

            /* for each symbol in the FIRST set of this rhs */
            NFirst  = SymbolListCount(Rule->First);
            for(iFirst = 0; iFirst < NFirst; ++iFirst)
                {
                InputToken   = SymbolListGet(Rule->First, iFirst);
                if(SymbolGetBit(InputToken, SYM_TERMINAL))
                    ErrorCount += AddLLTableRule(NonTerm, InputToken, iRule);
                }
            /* if FIRST(rhs) contains epsilon */
            if(Rule->Nullable)
                {
                int     NFollow, iFollow;

                /* handle terminals in FOLLOW set of non-terminal */
                NFollow = SymbolListCount(NonTerm->Follow);
                for(iFollow = 0; iFollow < NFollow; ++iFollow)
                    {
                    InputToken  = SymbolListGet(NonTerm->Follow, iFollow);
                    if(SymbolListContains(Rule->First, InputToken))
                        {
/*???TODO???*/
                        fprintf(stderr, "Can't happen: nonterm '%s', rule '%d' first/follow clash on %s\n",
                              SymbolStr(NonTerm), iRule, SymbolStr(InputToken));
                        }
                    if(SymbolGetBit(InputToken, SYM_TERMINAL))
                        AddLLTableRule(NonTerm, InputToken, iRule);
                    }
                }
            }
        }
    if(ErrorCount)
        Exit(-1, ERROR_LL_CONFLICT);
    }

#if 0
void    ComputeOperators(void)
    {
    int         NNonTerms, iTerm, iRule;
    TSymbol*    NonTerm;
    TSymbol*    InputToken;

    NNonTerms      = SymbolListCount(Globals.NonTerms);
    for(iTerm = 0; iTerm < NNonTerms; ++iTerm)
        {
        NonTerm     = SymbolListGet(Globals.NonTerms, iTerm);
        /* if it's not an operator grammar start symbol */
        if(!NonTerm->OperatorTrigger)
            continue;   /* then skip it */
        
fprintf(stderr, "THis code ain't writ yet!\n\n\n--\n");
        /* for each rule of the operator trigger */
        for(iRule = 0; iRule < NonTerm->NRules; ++iRule)
            {
            int         NFirst, iFirst;
            TRule*      Rule = NonTerm->Rules[iRule];

            NFirst  = SymbolListCount(Rule->First);
            for(iFirst = 0; iFirst < NFirst; ++iFirst)
                {
                InputToken   = SymbolListGet(Rule->First, iFirst);
                if(SymbolGetBit(InputToken, SYM_TERMINAL))
                    AddLLTableRule(NonTerm, InputToken, iRule);
                }
            if(Rule->Nullable)
                {
                int     NFollow, iFollow;

                NFollow = SymbolListCount(NonTerm->Follow);
                for(iFollow = 0; iFollow < NFollow; ++iFollow)
                    {
                    InputToken  = SymbolListGet(NonTerm->Follow, iFollow);
                    if(SymbolGetBit(InputToken, SYM_TERMINAL))
                        AddLLTableRule(NonTerm, InputToken, iRule);
                    }
                }
            }
        }
    }

#endif
/*************************************************************
 * Computing operator precedence table
 *************************************************************/

void ComputePrecTable(void)
    {
    }

/* LeftRecurSyms() - Locate symbols involved in left recursion, if any.
 *
 * This = top of Stack
 * 
 * for each proditem of each rule
 *     if(proditem is action)
 *         continue
 *     else if(proditem is terminal)
 *         break
 *     if(proditem == Root)
 *         add Stack to Found
 *         continue
 *     if(proditem not in Checked)
 *         push proditem on Stack
 *         add LeftRecurSyms() to Found
 *     if(proditem not nullable)
 *         break
 *                 
 * pop Stack
 * return Found
 */
SYMBOLS LeftRecurSyms(TSymbol* Root, SYMBOLS Stack, SYMBOLS Checked)
    {
    TSymbol*    This;
    RuleIt      Rules;
    SYMBOLS     Found = NULL;

    DumpVerbose("LeftRecurSyms('%s', %d, %d)\n", SymbolStr(Root), SymbolListCount(Stack), SymbolListCount(Checked));

    /* initialization for first invocation */
    if(Stack == NULL)
        {
        assert(Checked == NULL);
        Stack       = SymbolListAdd(NULL, Root);
        Checked     = SymbolListCreate();
        }

    This  = SymbolListTop(Stack);
    if(SymbolListContains(Checked, This) || SymbolIsEmpty(This))
        {
        DumpVerbose("LeftRecurSyms('%s', %d, %d) skips %s\n", SymbolStr(Root), SymbolListCount(Stack), SymbolListCount(Checked), SymbolStr(This));
        return NULL;
        }
    else
        Checked = SymbolListAdd(Checked, This);

    /* for every production item in every rule */
    for(Rules = RuleItNew(This); RuleIterate(&Rules); )
        if(SymbolGetBit(Rules.ProdItem, SYM_TERMINAL))
            RuleItNext(&Rules);  /* go to next rule; this rule can't lead to left recursion */
        else
            {
            if(Rules.ProdItem == Root)
                SymbolListAddList(&Found, Stack);
            else
                {
                Stack   = SymbolListPush(Stack, Rules.ProdItem);
                SymbolListAddList(&Found, LeftRecurSyms(Root, Stack, Checked));
                }
            }
    SymbolListPop(Stack);

    DumpVerbose("LeftRecurSyms('%s', %d, %d) returns %d\n", SymbolStr(Root), SymbolListCount(Stack), SymbolListCount(Checked), SymbolListCount(Found));

    if(SymbolListCount(Stack) == 0)
        {
        SymbolListDestroy(Checked);
        SymbolListDestroy(Stack);
        }

    return Found;
    }

/* GenerateComboNonTerm() - create a nonterminal from two other symbol names.
 *
 * This is used in the left corner transformation algorithm.
 */
static
TSymbol*    GenerateComboNonTerm(TSymbol* A, TSymbol* B)
    {
    TSymbol*    Combo;
    TToken      Token;

    Token   = TokenFake(TK_IDENT, "[%s-%s]", SymbolStr(A), SymbolStr(B));
    Combo   = SymbolFind(Token);
    if(!Combo)
        Combo   = SymbolNewNonTerm(Token);
    return Combo;
    }

/* GenerateUniqueNonTerm() - create a new nonterminal with a unique name.
 */

static
TSymbol*    GenerateUniqueNonTerm(TSymbol* NonTerm, char C)
    {
    int         Collision;
    TSymbol*    Unique;
    TToken      Token;
    char        Buffer[128];

//printf(".   GenerateUniqueNonTerm(%s) = ", SymbolStr(NonTerm));
    for(Collision=0; ; ++Collision)
        {
        int     iChar;

        for(iChar = 0; iChar <= Collision; ++iChar)
            Buffer[iChar]   = C;
        Buffer[iChar]   = '\0';
        Token   = TokenFake(TK_IDENT, "%s%.*s",
                            Buffer, NonTerm->Name.TextLen, NonTerm->Name.Text);
        if(!SymbolFind(Token))
            {
//printf("   '%.*s'\n", Token.TextLen, Token.Text);
            Unique  = SymbolNewNonTerm(Token);
            break;
            }
        assert(Collision < 127);
        }
    return Unique;
    }

#if 0
/* RemoveLeftRecursion() - rewrite a nonterminal to remove left recursion.
 *
 * The caller has identified for us which rules are left recursive and which
 * are not. Suppose the original nonterminal looks like this:
 *
 *     A : A x
 *       | x
 *       ;
 *
 * Then our rewritten grammar would be:
 * 
 *     `A : x `A
 *        | ;
 *     A : x `A
 *       ;
 */
static
void    RemoveLeftRecursion(TSymbol* NonTerm, TRule**Left, int NLeft)
    {
    int         iRule, jRule;
    TSymbol*    NewNonTerm;
    
    fprintf(stdout, ">>>>>>>remove %d left-recursive rules from  '%.*s'\n",
            NLeft,
                NonTerm->Name.TextLen, NonTerm->Name.Text);
DumpTreeSymbol(NonTerm, FALSE);
    /* create new non-terminal to hold recursive tails */
    NewNonTerm  = GenerateUniqueNonTerm(NonTerm, '`');

    /* now modify the rules of the original nonterminal */
    for(iRule = jRule = 0; iRule < NonTerm->NRules; ++iRule)
        {
        TRule*  Rule    = NonTerm->Rules[iRule];


        if(IsLeftRecursive(Rule, NonTerm))
            continue;
        /* else, this rule is not left-recursive, but must be modified */
        else
            {
            /* copy into its new position */
            NonTerm->Rules[jRule] = Rule;
            /* and make it end new, synthesized nonterminal */
            Rule->Symbols   = SymbolListAdd(Rule->Symbols, NewNonTerm);
            ++jRule;
            Rule->TailRecursive = 1;
            }
        }
    assert(jRule == NonTerm->NRules - NLeft);
    NonTerm->NRules = jRule;    /* correct the count of rules */

    /* give the new nonterminal all the left-recursive rules */
    NewNonTerm->NRules  = NLeft;
    NewNonTerm->Rules   = Left;

    /* but make them right-recursive */
    for(iRule = 0; iRule < NLeft; ++iRule)
        {
        TSymbol*    Dummy;
        TRule*      Rule    = Left[iRule];

        Dummy   = SymbolListDelete(Rule->Symbols, 0);
        assert(Dummy == NonTerm);
        Rule->Symbols   = SymbolListAdd(Rule->Symbols, NewNonTerm);
        Rule->TailRecursive = 2;
        }

    /* and add empty production */
    SymbolNewRule(NewNonTerm);
    /* and mark it nullable! (we're not calling MarkNullable() a 2nd time)*/
    NewNonTerm->Nullable = TRUE;
DumpTreeSymbol(NonTerm, FALSE);
DumpTreeSymbol(NewNonTerm, FALSE);
    }
#else

/* AddLeftCorners() - add left corners of NonTerm to symbol list.
 *
 * By left corners, we mean the transitive closure of
 * the direct left corner relationship. 
 *
 */
SYMBOLS AddLeftCorners(SYMBOLS LeftCorners, TSymbol* NonTerm)
    {
    int         iSymbol, NProdItems, iProdItem;
    TSymbol*    Symbol;
    TRule**     Rover;
    TRule*      Rule;

    LeftCorners   = SymbolListAddUnique(LeftCorners, NonTerm);

    for(iSymbol = 0; iSymbol < SymbolListCount(LeftCorners); ++iSymbol)
        {
        Symbol = SymbolListGet(LeftCorners, iSymbol);

        /* For each rule of this non-terminal */
        Rover   = Symbol->Rules;
        if(Rover) for(; (Rule=*Rover) != NULL; ++Rover)
            {
            NProdItems  = SymbolListCount(Rule->Symbols);
            for(iProdItem = 0; iProdItem < NProdItems; ++iProdItem)
                {
                TSymbol*    ProdItem;

                ProdItem    = SymbolListGet(Rule->Symbols, iProdItem);
                LeftCorners = SymbolListAddUnique(LeftCorners, ProdItem);
                break;
                if(SymbolIsAction(ProdItem))
                    continue;
                if(!ProdItem->Nullable)
                    break;
                }
            }
        }
    
    if(Globals.Dump && Globals.Verbose)
        {
        DumpVerbose("LeftCorner('%s')=", SymbolStr(NonTerm));
        SymbolListDump(stdout, LeftCorners, ", ");
        DumpVerbose("\n");
        }

    return LeftCorners;
    }

/* LCXFormTerminal() - create left-corner transformation rule for a terminal.
 *
 * Original non-terminal had a terminal ("a") in its left corner,
 * so we create this:
 *     A -> a A-a
 */
static TRule* LCXFormTerminal(SYMBOLS SubGrammar, TSymbol* NonTerm, TSymbol* Terminal)
    {
    TRule*      NewRule = SymbolNewRule(NonTerm);
    TSymbol*    Synth   = GenerateComboNonTerm(NonTerm, Terminal);

    DumpVerbose("'%s' had terminal '%s' in its left corner, so create %s : %s [%s-%s]\n",
        SymbolStr(NonTerm), SymbolStr(Terminal), SymbolStr(NonTerm), SymbolStr(Terminal), SymbolStr(NonTerm), SymbolStr(Terminal));
    RuleAddSymbol(NewRule, Terminal, Terminal->Name);
    RuleAddSymbol(NewRule, Synth, Synth->Name);

    SubGrammar = SymbolListAddUnique(SubGrammar, Synth);
    return NewRule;
    }

/* LCXFormNullable() - create left-corner transformation rule for nullable non-terminal
 *
 * Original non-terminal had a non-terminal ("C") containing an epsilon production
 * in its left corner, so we create this:
 *     A -> A-C
 * Note that it doesn't matter if "C" happens to be "A".
 */
static TRule* LCXFormNullable(SYMBOLS SubGrammar, TSymbol* A, TSymbol* C)
    {
    TRule*      NewRule = SymbolNewRule(A);
    TSymbol*    Synth   = GenerateComboNonTerm(A, C);

    DumpVerbose("'%s' had epsilon-producing '%s' in its left corner, so create %s : [%s-%s]\n",
        SymbolStr(A), SymbolStr(C), SymbolStr(A), SymbolStr(A), SymbolStr(C));

    RuleAddSymbol(NewRule, Synth, Synth->Name);
    SubGrammar = SymbolListAddUnique(SubGrammar, Synth);
    SubGrammar = SymbolListAddUnique(SubGrammar, C);

    return NewRule;
    }

/* LCXFormRule() - create left-corner transformation of rule.
 *
 * While processing non-terminal A, We found a production like this:
 *     B -> X beta
 * and must transform it to this:
 *     A-X -> beta A-B
 * Additionally, if this rule is from our root symbol, we need
 *     A-X -> beta
 * However, that is really the special case of tail recursion that
 * we want to optimize out. Therefore, in that case, we emit a single
 * single transformed production rather than two:
 *     A-A -> beta {} A-A
 * 
 */
static void LCXFormRule(SYMBOLS SubGrammar, TSymbol* A, TSymbol* B, TRule* OldRule)
    {
    TSymbol*    X;
    TSymbol*    AminusB;
    TSymbol*    AminusX;
    TRule*      NewRule;

    Dump("LCXFormRule(A=%s,B=%s)\n", SymbolStr(A), SymbolStr(B));
    /* create and remember new non-terminal named "A-B" */
    AminusB     = GenerateComboNonTerm(A, B);
    SubGrammar  = SymbolListAddUnique(SubGrammar, AminusB);
    NewRule     = RuleDup(OldRule);
#if 0
    while((X=RuleRemoveSymbol(NewRule, 0)) != NULL)
        if(!SymbolIsAction(X))
            break;
#else
    X   = RuleRemoveSymbol(NewRule, 0);
#endif
    assert(X != NULL);

    Dump("    removed X = '%s'\n", SymbolStr(X));
    /* create and remember new non-terminal named "A-X" */
    AminusX     = GenerateComboNonTerm(A, X);
    SubGrammar  = SymbolListAddUnique(SubGrammar, AminusX);

    if(A == B)
        {
// ??? add marker non-term for left recursion
        RuleAddSymbol(NewRule, SymbolFind(ReduceToken), ReduceToken);
        RuleAddSymbol(NewRule, AminusB, AminusB->Name);
        }
    else
        {
        RuleAddSymbol(NewRule, AminusB, AminusB->Name);
        }

    SymbolAddRule(AminusX, NewRule);

    Dump("LCXFormRule() returns\n");
    }



/* RemoveLeftRecursion() - rewrite a nonterminal to remove left recursion.
 *
 * TODO: this code is not right. Could be multiple left recursions that share
 * a common "innocent" rule(s).
 *
 * Use a left-corner transformation to rewrite this non-terminal
 * (and possibly others) to remove left recursion (note that
 * new rules with common left factors may be introduced).
 *
 */
static void    RemoveLeftRecursion(TSymbol* Root)
    {
    SYMBOLS     SubGrammar          = NULL;
    SYMBOLS     LeftCorners   = NULL;
    SymIt       Corner;
    TRule*      OldRule;
    TRule**     Rover;
    
    if(Globals.Dump && Globals.Verbose)
        {
        DumpVerbose(">>>>>>>remove left-recursion starting at '%s'\n", SymbolStr(Root));
        DumpTreeSymbol(Root, FALSE);
        }

    /* find the left corners of this root */
    LeftCorners   = AddLeftCorners(LeftCorners, Root);
    assert(SymbolListContains(LeftCorners, Root));

    /* keep track of all non-terminals in transformed sub-grammar */
    SubGrammar  = SymbolListAdd(NULL, Root);

    /* wipe out rules, but first save in a safe spot    */
    Root->OrigRules = Root->Rules;
    Root->Rules     = NULL;

    /* for each symbol that is in "full" left corner of Root */
    Corner  = SymItNew(LeftCorners);
    while(SymbolIterate(&Corner))
        {
        DumpVerbose("Processing left corner '%s'\n", SymbolStr(Corner.Symbol));

        /* if it's a terminal */
        if(SymbolGetBit(Corner.Symbol, SYM_TERMINAL))
            LCXFormTerminal(SubGrammar, Root, Corner.Symbol);
        else if(SymbolIsAction(Corner.Symbol))
            LCXFormTerminal(SubGrammar, Root, Corner.Symbol);
        /* else it's a non-terminal */
        else
            {
            SubGrammar = SymbolListAddUnique(SubGrammar, Corner.Symbol);
            Rover   = Corner.Symbol->OrigRules ? Corner.Symbol->OrigRules : Corner.Symbol->Rules;
            assert(Rover != NULL);
            assert(*Rover != NULL);     /* sanity check: must have at least one rule! */
            /* for each rule in this non-terminal */
            for(; *Rover; ++Rover)
                {
                OldRule    = *Rover;
#if 0
                if(RuleItemCount(OldRule) == 0)
                    LCXFormNullable(SubGrammar, Root, Corner.Symbol);
                if(RuleItemCount(OldRule) == 0)
                    {
                    /* if root has epsilon production, must copy it verbatim */
                    if(Corner.Symbol == Root)
                        SymbolDupRule(Root, OldRule);
                    }
                /* else rule has at least one symbol */
                else
#endif
                    LCXFormRule(SubGrammar, Root, Corner.Symbol, OldRule);
                }
            }
        }
    if(Globals.Dump && Globals.Verbose)
        {
        SymIt   NonTerms;

        DumpVerbose("Rewritten '%s' is: \n", SymbolStr(Root));
        NonTerms    = SymItNew(SubGrammar);
        while(SymbolIterate(&NonTerms))
            DumpTreeSymbol(NonTerms.Symbol, FALSE);
        }
    SymbolListDestroy(LeftCorners);
    DumpVerbose("<<<<<<<\n");

    }
#endif
/* CommonRhs() - report length of right-hand-side common prefix in two rules.
 *
 * This function determines whether two rules are candidates for
 * left factoring. However, it also performs three important error
 * checks.
 *
 * First, it is an error if two rules have right-hand-sides
 * with identical sequences of symbols (modulo actions).
 *
 * Second, it is an error if two rules have prefixes that
 * differ only because of embedded actions.
 *
 * Third, it is an error if two rules with common prefixes
 * have suffixes that cannot be distinguished.
 */

static
int     FindShortestPrefix(TSymbol* NonTerm)
    {
    int     Shortest    = 0;
    TRule** Rules       = NonTerm->Rules;
    int     NRules      = RuleCount(NonTerm);
    int     iRule;

    /* scan all the rules */
    for(iRule = 0; iRule < NRules; ++iRule)
        {
        TRule*  Rule    = Rules[iRule];

        /* if this rule has a prefix in common with another rule */
        if(Rule->LeftFactor > 0)
            {
            if(Shortest == 0 || Rule->LeftFactor < Shortest)
                Shortest    = Rule->LeftFactor;
            if(Shortest == 1)   /* can't get any shorter than that! */
                break;
            }
        }
//fprintf(stderr, "FindShortestPrefix returns %d\n", Shortest);
    return Shortest;
    }

/* NumberCommonLeft() - assign common left factor length to each rule.
 *
 * Assign each rule a number equal to the length of the largest
 * prefix it has in common with other rules from this nonterminal.
 * Ignore nonterminals that are placeholders for actions at this stage.
 */
static
void    NumberCommonLeft(TSymbol* NonTerm)
    {
    TRule** Rules;
    int     NRules;
    int     iRule;
    int     HighScore   = 0;
    
    NRules  = RuleCount(NonTerm);
    Rules   = NonTerm->Rules;

    /* initialize length of longest common left factor to zero
     */
    for(iRule = 0; iRule < NRules; ++iRule)
        Rules[iRule]->LeftFactor    = 0;

    for(iRule = 0; iRule < (NRules-1); ++iRule)
        {
        int         jRule, Score;
        TRule*      RuleA = Rules[iRule];

        /* compare each rule to those after it  */
        for(jRule = iRule+1; jRule < NRules; ++jRule)
            {
            TRule*      RuleB = Rules[jRule];

            Score   = CommonLeft(NonTerm, RuleA->Symbols, RuleB->Symbols);
            if(Score > RuleA->LeftFactor)
                RuleA->LeftFactor   = Score;
            if(Score > RuleB->LeftFactor)
                RuleB->LeftFactor   = Score;
            if(Score > HighScore)
                HighScore   = Score;
            }
        }

    if(Globals.Dump && HighScore)
        printf("        '%.*s' has one or more rules with common left prefixes of length %d.\n",
               NonTerm->Name.TextLen, NonTerm->Name.Text, HighScore);
    }

/* RuleMoveSuffix() - use suffix from one rule to make a new rule.
 *
 * Called during left factoring to clip the suffix from
 * a rule and use it to make a new rule in another nonterminal.
 */
static
void    RuleMoveSuffix(TRule* Rule, int PrefixLen, TSymbol* NewNonTerm)
    {
    int     iSymbol, nSymbols, Len;
    TRule*  NewRule;

//fprintf(stderr, "RuleMoveSuffix(PrefixLen=%d)\n", PrefixLen);

    /* create empty rule in target nonterminal */
    NewRule     = SymbolNewRule(NewNonTerm);

    /* locate first symbol of suffix */
    nSymbols    = SymbolListCount(Rule->Symbols);
//fprintf(stderr, ".   RuleMoveSuffix(PrefixLen=%d) nSymbols=%d\n", PrefixLen, nSymbols);
    for(Len = iSymbol = 0; iSymbol < nSymbols; ++iSymbol)
        {
        TSymbol*    Symbol = SymbolListGet(Rule->Symbols, iSymbol);

        if(!SymbolIsAction(Symbol))
            if(++Len >= PrefixLen)
                break;
        }
//fprintf(stderr, ".     prefix is %d symbols\n", iSymbol+1);
    /* move any remaining symbols over */
    for(++iSymbol; iSymbol < nSymbols; ++iSymbol)
        {
        TSymbol*    Symbol = SymbolListGet(Rule->Symbols, iSymbol);

        RuleAddSymbol(NewRule, Symbol, Rule->Tokens[iSymbol]);
        }
//fprintf(stderr, ".     New length is  %d symbols\n", SymbolListCount(Rule->Symbols));

    NewRule->RuleId = Rule->RuleId;
//fprintf(stderr, ".   new rule: %s -> ", SymbolStr(NewNonTerm));
//SymbolListDump(stderr, NewRule->Symbols, " ");
//fprintf(stderr, "\n");
    }

static
void    RuleRemove(TSymbol* NonTerm, int iRemove)
    {
    TRule** Rules       = NonTerm->Rules;
    TRule*  Rule;
    int     NRules      = RuleCount(NonTerm);
    int     iRule;

    assert(iRemove < NRules);
    assert(iRemove >= 0);
    
    Rule    = Rules[iRemove];
    RuleFree(Rule);

    /* shift all the other rules down */
    for(iRule = iRemove; iRule+1 < NRules; ++iRule)
        {
        Rules[iRule]    = Rules[iRule+1];
        }
    Rules[iRule]    = NULL;
    }

static
void    RuleTruncate(TRule* Rule, int PrefixLen)
    {
    int     iSymbol, nSymbols, Len;

    /* locate first symbol of suffix */
    nSymbols    = SymbolListCount(Rule->Symbols);
    for(Len = iSymbol = 0; iSymbol < nSymbols; ++iSymbol)
        {
        TSymbol*    Symbol = SymbolListGet(Rule->Symbols, iSymbol);

        if(!SymbolIsAction(Symbol))
            if(++Len >= PrefixLen)
                break;
        }
    
    SymbolListTruncate(Rule->Symbols, iSymbol+1);
    }


/* RewriteCommonLeft() - the basic unit of left-factoring.
 *
 * The caller knows that NonTerm contains two or more rules
 * with a common left factor of Length symbols. This function
 * locates the first such rule, then factors out that rule
 * and the one or more other rules that share the left factor
 * of that length. Example:
 *
 * A  : A B C D | A B C E
 *
 * becomes
 *
 * A   : A B C `A
 * `A  : D | E
 *
 * Note that Length alone does not uniquely identify a
 * group of rules with a common left factor:
 *
 * A
 *     : A B C D
 *     | A B C E
 *     | X Y Z D
 *     | X Y Z E
 *     ;
 *
 * The preceding grammar fragment contains two separate
 * groups of rules with common left factors of length 3.
 * That's OK; this function just rewrites the first group
 * of a given length that it runs into. The caller will
 * call us again with the same Length if necessary.
 *
 * Note also that common left factoring may leave more
 * factoring work to do:
 *
 * A   : A B C D | A B C E | A B F
 *
 * becomes
 * 
 * A   : A B #A
 * #A  : C D | C E | F
 *
 * And the revised version of nonterminal A still has
 * a common left factor. That's OK too; we keep removing
 * common left factors in a loop until none are left.
 */
static
void RewriteCommonLeft(TSymbol* NonTerm, int Length)
    {
    int         iRule, OrigRuleCount, iTarget;
    TRule**     Rules;
    TRule*      Rule;
    TSymbol*    NewNonTerm;
    
//printf(".RewriteCommonLeft('%s')\n", SymbolStr(NonTerm));
//fprintf(stderr, ".   Before left factoring, rule count = %d\n", NonTerm->NRules);

    /* locate first rule with common left factor of this length */
    Rules           = NonTerm->Rules;
    OrigRuleCount   = RuleCount(NonTerm);
    Rule    = NULL;
    for(iTarget = 0; iTarget < (OrigRuleCount-1); ++iTarget)
        {
        Rule   = Rules[iTarget];

        if(Rule->LeftFactor >= Length)
            break;
        }
//fprintf(stderr, ".   select rule %d to left factor: ", iTarget);
//SymbolListDump(stderr, Rule->Symbols, " ");
//fprintf(stderr, "\n");
    assert(Rule != NULL);
    
    /* generate a new nonterminal to hold unique tails of nonunique left prefixes */
    NewNonTerm  = GenerateUniqueNonTerm(NonTerm, '#');

    RuleMoveSuffix(Rule, Length, NewNonTerm);
    RuleTruncate(Rule, Length);
    RuleAddSymbol(Rule, NewNonTerm, EOFToken);  /* no real token available, so use EOF */

    /* NB: NRules may change during loop -- don't cache it in a local var! */
    for(iRule = 0; iRule < RuleCount(NonTerm); ++iRule)
        {
        if(iRule == iTarget)
            continue;
        if(CommonLeft(NonTerm, Rule->Symbols, Rules[iRule]->Symbols) >= Length)
            {
            RuleMoveSuffix(Rules[iRule], Length, NewNonTerm);
            RuleRemove(NonTerm, iRule);
            --iRule;
            }
        }
    /* must have removed at least one rule */
    assert(RuleCount(NonTerm) < OrigRuleCount);

    Rule->LeftFactor    = 0;    /* this rule can't be factored any more */

//fprintf(stderr, ".   After left factoring, rule count = %d\n", NonTerm->NRules);
    }


/* RewriteGrammar() - rewrite to attempt to achieve LL(1)ness.
 *
 * Here, we try to factor common left prefixes, and transform
 * direct left recursion into LL(1) constructs. Note that previous
 * code in checks.c have largely ignored these cases, so we
 * have to do checking here to ensure the candidate rules really
 * are something we can transform correctly and end up with an
 * LL(1) grammar.
 */
void    RewriteGrammar(void)
    {
    int         NNonTerms, iTerm, iRule;
    TSymbol*    NonTerm;
    SYMBOLS     LeftRecurs  = NULL;
    SymIt       NonTerms    = SymItNew(Globals.NonTerms);

    Dump(">RewriteGrammar().\n");

    NNonTerms      = SymbolListCount(Globals.NonTerms);

    Dump("  remove immediate left recursion.\n");

    while(SymbolIterate(&NonTerms))
        {
        SymbolListAddList(&LeftRecurs, LeftRecurSyms(NonTerms.Symbol, NULL, NULL));
        }
    printf("Found %d symbols involved in left recursion.\n", SymbolListCount(LeftRecurs));
    SymbolListDump(stdout, LeftRecurs, " ");
#if 0
    /* for each non-terminal... */
    for(iTerm = 0; iTerm < NNonTerms; ++iTerm)
        {
        TRule**     Left;
        int         NRules, NLeft, NNotLeft;

        NonTerm     = SymbolListGet(Globals.NonTerms, iTerm);

        /* Only looking for valid left-recursive non-terminals */
        if(NonTerm->OperatorTrigger || SymbolIsAction(NonTerm))
            continue;   /* then skip it */
        
        NRules  = RuleCount(NonTerm);

        /* Left will be an array of the left-recursive rules */
        Left    = malloc(NRules * sizeof(TRule*));

        /* for each rule of this non-terminal... */
        for(NLeft = NNotLeft = iRule = 0; iRule < NRules; ++iRule)
            {
            int         NProdItem;
            TRule*      Rule = NonTerm->Rules[iRule];

            assert(Rule != NULL);
            NProdItem   = SymbolListCount(Rule->Symbols);
            if(IsLeftRecursive(Rule, NonTerm))
                Left[NLeft++]       = Rule;
            }
        /* if we encountered one or more rules with immediate left-recursion */
#if 1
        if(NLeft > 0)
            RemoveLeftRecursion(NonTerm);
        else
            free(Left);
#endif
        }
#endif

    /* second, we rewrite to left factor the grammar */
    if(Globals.Dump)    printf("  left factor grammar.\n");
    for(iTerm = 0; iTerm < SymbolListCount(Globals.NonTerms); ++iTerm)
        {
        int         NRules;
        int         PrefixLen;

        NonTerm     = SymbolListGet(Globals.NonTerms, iTerm);

        /* skip nonterminals irrelevant to rewriting    */
        if(NonTerm->OperatorTrigger || SymbolIsAction(NonTerm))
            continue;   /* then skip it */
        
        NRules  = RuleCount(NonTerm);

        NumberCommonLeft(NonTerm);
        PrefixLen   = FindShortestPrefix(NonTerm);
        for(iRule = 0; PrefixLen > 0; ++iRule)
            {
            assert(iRule < NRules);

            RewriteCommonLeft(NonTerm, PrefixLen);

            PrefixLen   = FindShortestPrefix(NonTerm);
            assert(iRule < NRules);
            }
        }
    if(Globals.Dump)    printf("<RewriteGrammar().\n");
//exit(0);
    }

